from re import X

from sympy import false


class DSU:  # 封装的
    def __init__(self, n: int):
        self.fa = list(range(n + 1))

    def find(self, x: int) -> int:
        if x == self.fa[x]:
            return x
        else:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]

    def merge(self, x: int, y: int) -> bool:  # 合并，x与y在同一集合返回False
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        self.fa[x] = y
        return True


# 未封装的，码量小
fa = []


def init(n: int):
    global fa
    fa = list(range(n + 1))


def find(x: int) -> int:
    if x == fa[x]:
        return x
    else:
        fa[x] = find(fa[x])
        return fa[x]


def merge(x: int, y: int) -> bool:
    x, y = find(x), find(y)
    if x == y:
        return False
    fa[x] = y
    return True
